package binary_tree.sort;

public class sevenSort {
    public void heapSort(int[] arr){
        //将数组最大堆
        for(int i=(arr.length-1-1)/2;i>=0;i--){
            siftDown(arr,i,arr.length);
        }
        //将堆顶元素与最后面的元素交换
        //再将交换后的堆最大堆
        //第一次是arr[0,arr.length-1]，转换后是arr[]
        //第二次是arr[0,arr.length-2],转换后的是arr[arr.length-1]
        //i代表的是此时数组的长度
        for(int i=arr.length-1;i>0;i--){
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }
    public void bubbleSort(int[] arr){
        //-1是因为当整个数组只剩下一个元素时，数组以及有序
        for(int i=0;i<arr.length-1;i++){
            boolean isSweaped=false;
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    isSweaped=true;
                    swap(arr,j,j+1);
                }
            }
            if(!isSweaped){
                //当内存循环没有数要进行交换时，跳出循环。
                break;
            }
        }
    }
    private void siftDown(int[] arr, int i, int n) {
        //当存在子树时
        while((i*2)+1<n){
            //j为子树的值
            int j=i*2+1;
            //右孩子存在并且小于左孩子
            if(j+1<n&&arr[j+1]>arr[j]){
                j=j+1;
            }
            //交换父节点与左右孩子中大的那个数
            if(arr[i]>=arr[j]){
                break;
            }else{
                swap(arr,i,j);
                //将i的值赋给j继续进行下一步操作
                i=j;
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

}
